package sudoku

// 解题
func Solve(cells []int) int {

	dlx := NewDlx(cells)

	cover := dlx.AnySolution()
	for _, step := range cover {
		index, value := parseStepOption(step.Option)
		cells[index] = value
	}

	count := 0
	dlx.GenerateSolutions(func([]Step) bool {
		count++
		return count <= 2
	})

	return count
}

// 解析
func parseStepOption(option int) (index int, value int) {
	return int(option / 9), option%9 + 1
}

// 实例化一个舞蹈链算法对象
func NewDlx(cells []int) *DLX {
	matrix := make([][]bool, 9*9*9)

	for n := range matrix {
		matrix[n] = make([]bool, 9*9*4)

		d := n % 9
		m := int(n / 9)
		x := int(n/9) % 9
		y := int(int(n/9)/9) % 9
		b := int(y/3)*3 + int(x/3)

		// 每个格子只能填一个数字
		matrix[n][m] = true
		// 每行只能填一个数字
		matrix[n][y*9+d+81*1] = true
		// 每列只能填一个数字
		matrix[n][x*9+d+81*2] = true
		// 每宫只能填一个数字
		matrix[n][b*9+d+81*3] = true
	}

	dlx := FromMatrix(matrix)

	for index, cell := range cells {
		if cell > 0 {
			dlx.ForceOptions(index*9 + cell - 1)
		}
	}

	return dlx
}
